/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/13
 * \* Time: 19:32
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 在D天内送达包裹的能力 {
    public int shipWithinDays(int[] weights, int days) {
        int left=1;
        int right=getMax(weights)+1;
//        //如果数组中最大重量无法满足，则直接从最大开始递增
//        if(!canFinish(weights,right-1,days)){
//            right++;
//            while (!canFinish(weights,right,days)){
//                right++;
//            }
//            return right;
//        }
        //如果数组中最大重量无法满足，则直接从最大开始×2，这个方法比上面的算法时间效率从打败6%上升到70%
        while (!canFinish(weights,right,days)){
            right*=2;
        }
        while (left<right){
            int mid=left+(right-left)/2;
            if(canFinish(weights,mid,days)){
                right=mid;
            }else if(!canFinish(weights,mid,days)){
                left=mid+1;
            }
        }
        return left;
    }

    int getMax(int[] weights){
        int max=-1;
        for(int n:weights){
            if(n>max){
                max=n;
            }
        }
        return max;
    }

    boolean canFinish(int[] weights,int mid,int days){
        int i=0;
        for(int day=0;day<days;day++){
            int maxCap=mid;
            while ((maxCap-=weights[i])>=0){
                i++;
                if(i==weights.length){
                    return true;
                }
            }
        }
        return false;
    }
}